home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8255 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.7 KB  |  116 lines
  1. Path: news.clark.net!usenet
  2. From: yom@clark.net (yom)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: need psudeo code for binary search
  5. Date: 1 Mar 1996 01:41:49 GMT
  6. Organization: home
  7. Message-ID: <4h5kkt$i31@clarknet.clark.net>
  8. References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix>
  9. NNTP-Posting-Host: yom.clark.net
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=US-ASCII
  12. X-Newsreader: WinVN 0.99.7
  13.  
  14. Here's the actual code I wrote some years ago.
  15.  
  16. Song (yom@clark.net)
  17.  
  18. /*
  19.     This function performs a binary search for a key in a sorted table and
  20.     returns the key index value if found.  The routine behaves similarly
  21.     to the standard library bsearch function except for added capabilities
  22.     of convergence and directional search.
  23. */
  24.  
  25. #include <string.h>
  26.  
  27. #define GE 1
  28. #define EQ 0
  29. #define LE -1
  30. #define NOTFOUND -1
  31.  
  32. int binsearch (void *key,int ksize,void *base,int nel,int bsize,int mode,
  33.                int (*compare)(void *,void *))
  34. {
  35.     int jl = 0;
  36.     int ju = nel - 1;
  37.     int jm;
  38.     int diff = 1;
  39.     int idx = NOTFOUND;
  40.     int tidx;
  41.     void *bl = (char *) base;
  42.     void *bu = (char *) base + (ju * bsize);
  43.  
  44. /*
  45.     Calculate the key index value.  If the input key value is within the
  46.     range of base, conduct bisection method search.  Otherwise, set the
  47.     key index value to minimum or maximum value of base depending on the
  48.     mode.
  49. */
  50.  
  51.     if (compare(key,bl) >= 0 && compare(key,bu) <= 0)
  52.     {
  53.         while (diff && ju >= jl)
  54.         {
  55.             jm = (ju + jl) / 2;
  56.             diff = compare(key,(char *) base + (jm * bsize));
  57.             if (diff > 0)
  58.                 jl = jm + 1;
  59.             else if (diff < 0)
  60.                 ju = jm - 1;
  61.         }
  62.         if (!diff)
  63.             idx = jm;
  64.         else if (mode == GE)
  65.             idx = diff < 0 ? jm : jm + 1;
  66.         else if (mode == LE)
  67.             idx = diff > 0 ? jm : jm - 1;
  68.     }
  69.     else if (mode == GE && compare(key,bl) < 0)
  70.         idx = jl;
  71.     else if (mode == LE && compare(key,bu) > 0)
  72.         idx = ju;
  73.  
  74. /*
  75.     Update the key value and converge via recursion if necessary.
  76. */
  77.  
  78.     if (idx != NOTFOUND)
  79.     {
  80.         if (diff)
  81.             memcpy(key,(char *) base + (idx * bsize),ksize);
  82.         if (idx > 0)
  83.         {
  84.             tidx = binsearch(key,ksize,base,idx,bsize,EQ,compare);
  85.             if (tidx != NOTFOUND)
  86.                 idx = tidx;
  87.         }
  88.     }
  89.  
  90.     return idx;
  91. }
  92.  
  93.  
  94.  
  95. In article <Pine.SOL.3.91.960229154211.27358B-100000@obelix>, 
  96. brown1@gaul.csd.uwo.ca says...
  97. >
  98. >
  99. >Does any one have some psudeocode /code (C) for a binary search using 
  100. >arrays of chars.
  101. >
  102. >any sugesstions on book or file locations would be appriciated.
  103. >
  104. >
  105. >If possible could anyopne who can help out mail me the info.
  106. >
  107. >brown1@gaul.csd.uwo.ca
  108. >
  109. >
  110. >thanks in advance.
  111. >
  112. >chris
  113. >
  114. >
  115.  
  116.